package leetcode.code0372;

import leetcode.helper.MaxDebug;

/**
 * 执行用时：4 ms, 在所有 Java 提交中击败了80.52%的用户
 *
 * 内存消耗：38.7 MB, 在所有 Java 提交中击败了35.99%的用户
 *
 * @author CaoYu
 * @date 2021年12月5日
 * @description
 */
public class Solution1 extends S372 {

	private int Mod = 1337;

	@Override
	public int superPow(int a, int[] b) {
		if (a == 1)
			return 1;
		int Len = b.length;
		long[] basic = new long[Len];
		basic[Len - 1] = a;
		for (int i = Len - 2; i >= 0; i--) {
			basic[i] = pow(basic[i + 1], 10) % Mod;
		}
		long ans = 1;
		for (int i = 0; i < Len; i++) {
			ans = ans * pow(basic[i], b[i]) % Mod;
		}
		return (int) ans;
	}

	private long pow(long basic, int n) {
		if (n == 0) {
			return 1;
		}
		long b = pow(basic, n >> 1) % Mod;
		return (n & 1) == 0 ? b * b : b * b * basic;
	}

	public static void main(String[] args) {
		Solution1 so = new Solution1();
		so.debug5();
		so.debug4();
		MaxDebug.debug14(so);

	}

}
